/*
 * Copyright (c) 2009, Andrey Shvetsov
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

/*
 * This is version of xintlib with recursive templates.
 * To use this version fix content of 'xintlib.h'
 */

#ifndef _XINTLIB1_H
#define	_XINTLIB1_H


namespace xintlib {

    template <class UNIT, int N>
    struct base_algo
    {
        typedef base_algo<UNIT,N-1> _next;

        static void set(UNIT *p, UNIT u = 0) {
            *p = u;
            _next::set( p+1 );
        }

        static void copy(UNIT *pl, const UNIT *pr) {
            *pl = *pr;
            _next::copy( pl+1 , pr+1 );
        }

        static void inc(UNIT *p) {
            if( UNIT( ++*p ) < 1 )
                _next::inc( p+1 );
        }

        static void add(UNIT *pl, const UNIT *pr, UNIT carry = 0) {
            UNIT const u = *pr + carry;
            _next::add( pl+1, pr+1, ( u < carry || ( *pl += u ) < u )? 1: 0 );
        }

        static void sub(UNIT *pl, const UNIT *pr, UNIT carry = 1) {
            UNIT const u = (~*pr) + carry;
            _next::sub( pl+1, pr+1, ( u < carry || ( *pl += u ) < u )? 1: 0 );
        }

        static bool sign_lt(const UNIT *pl, const UNIT *pr, UNIT mask) {
            if( *--pl != *--pr )
                return (mask ^ *pl) < (mask ^ *pr);
            return _next::lt( pl, pr );
        }

        static bool lt(const UNIT *pl, const UNIT *pr) {
            if( *--pl != *--pr )
                return *pl < *pr;
            return _next::lt( pl, pr );
        }

        static bool sign_lteq(const UNIT *pl, const UNIT *pr, UNIT mask) {
            if( *--pl != *--pr )
                return (mask ^ *pl) < (mask ^ *pr);
            return _next::lteq( pl, pr );
        }

        static bool lteq(const UNIT *pl, const UNIT *pr) {
            if( *--pl != *--pr )
                return *pl < *pr;
            return _next::lteq( pl, pr );
        }

        static bool eq(const UNIT *pl, const UNIT *pr) {
            return *--pl == *--pr && _next::eq( pl, pr );
        }

        template <class T>
        static T &for_each(UNIT *p, T &t) {
            t( *--p );
            return _next::for_each( p, t );
        }

        template <class T>
        static T &for_each_r(UNIT *p, T &t) {
            t( *p );
            return _next::for_each_r( p+1, t );
        }
    };

    template <class UNIT>
    struct base_algo<UNIT,0> {
        static void set(UNIT *) {}
        static void copy(UNIT *, const UNIT *) {}
        static void inc(UNIT *) {}
        static void add(UNIT *, const UNIT *, UNIT) {}
        static void sub(UNIT *, const UNIT *, UNIT) {}
        static bool lt(const UNIT *, const UNIT *) { return false; }
        static bool lteq(const UNIT *, const UNIT *) { return true; }
        static bool eq(const UNIT *, const UNIT *) { return true; }
        template <class T>
        static T &for_each(UNIT *, T &t) { return t; }
        template <class T>
        static T &for_each_r(UNIT *, T &t) { return t; }
    };

} // namespace xintlib


namespace xintlib {

    template<int MIN_NBITS, class UNIT = unsigned, int BITS_PRO_CHAR = 8>
    struct xint
    {
        enum {
            BITS_PRO_UINT = sizeof(UNIT) * BITS_PRO_CHAR,
            N = (MIN_NBITS+BITS_PRO_UINT-1)/BITS_PRO_UINT
        };

        typedef UNIT unit_type;
        typedef base_algo<UNIT,N> algo;
        typedef base_algo<const UNIT,N> const_algo;

        xint(UNIT u = 0) {
            algo::set( raw_array, u );
        }

        xint(const xint &x) {
            algo::copy( raw_array, x.raw_array );
        }

        xint &operator+=(const xint &x) {
            algo::add( raw_array, x.raw_array );
            return *this;
        }

        xint &operator-=(const xint &x) {
            algo::sub( raw_array, x.raw_array );
            return *this;
        }

        bool operator<(const xint &x) const {
            UNIT const mask = UNIT(1) << ( BITS_PRO_UINT - 1 );
            return algo::sign_lt( raw_array + N, x.raw_array + N, mask );
        }

        bool operator<=(const xint &x) const {
            UNIT const mask = UNIT(1) << ( BITS_PRO_UINT - 1 );
            return algo::sign_lteq( raw_array + N, x.raw_array + N, mask );
        }

        bool operator==(const xint &x) const {
            return algo::eq( raw_array + N, x.raw_array + N );
        }

        UNIT raw_array[N];
    };

} // namespace xintlib


namespace xintlib {

    template<class XINT>
    inline bool operator>(const XINT &a, const XINT &b) {
        return !( a <= b );
    }

    template<class XINT>
    inline bool operator>=(const XINT &a, const XINT &b) {
        return !( a < b );
    }

    template<class XINT>
    inline bool operator!=(const XINT &a, const XINT &b) {
        return !( a == b );
    }

    template<class XINT>
    inline XINT operator+(const XINT &a, const XINT &b) {
        return XINT( a ) += b;
    }

    template<class XINT>
    inline XINT operator-(const XINT &a, const XINT &b) {
        return XINT( a ) -= b;
    }

    template<class XINT>
    inline XINT operator-(const XINT &x) {
        return XINT() -= x;
    }

    template<class XINT>
    inline XINT operator+(const XINT &x) {
        return XINT( x );
    }

} // namespace xintlib


namespace xintlib {

    template <class XINT, class T>
    inline T &for_each_unit(XINT &x, T &t) {
        return XINT::algo::for_each( x.raw_array + XINT::N, t );
    }

    template <class XINT, class T>
    inline const T &for_each_unit(XINT &x, const T &t) {
        return XINT::algo::for_each( x.raw_array + XINT::N, t );
    }

    template <class XINT, class T>
    inline T &for_each_unit(const XINT &x, T &t) {
        return XINT::const_algo::for_each( x.raw_array + XINT::N, t );
    }

    template <class XINT, class T>
    inline const T &for_each_unit(const XINT &x, const T &t) {
        return XINT::const_algo::for_each( x.raw_array + XINT::N, t );
    }

    template <class XINT, class T>
    inline T &for_each_unit_r(XINT &x, T &t) {
        return XINT::algo::for_each_r( x.raw_array, t );
    }

    template <class XINT, class T>
    inline const T &for_each_unit_r(XINT &x, const T &t) {
        return XINT::algo::for_each_r( x.raw_array, t );
    }

    template <class XINT, class T>
    inline T &for_each_unit_r(const XINT &x, T &t) {
        return XINT::const_algo::for_each_r( x.raw_array, t );
    }

    template <class XINT, class T>
    inline const T &for_each_unit_r(const XINT &x, const T &t) {
        return XINT::const_algo::for_each_r( x.raw_array, t );
    }

} // namespace xintlib


#endif	/* _XINTLIB1_H */
